package com.zj.leetcode.medium.greed;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @program: algorithm
 * @description: 移掉 K 位数字
 * 402 remove-k-digits
 * @author: Zhang Bo
 * @create: 2022-04-18 10:39:41
 **/
public class RemoveKDigits {
    public static void main(String[] args) {
        Solution solution = new RemoveKDigits().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 输入：num = "1432219", k = 3 length = 7
         * 输出："1219"
         * <p>
         * 输入：num = "10200", k = 1 length = 5
         * 输出："200"
         * <p>
         * 输入：num = "10", k = 2 length = 2
         * 输出："0"
         * <p>
         * 结论（杰伦）解题方法：
         * 贪心的思想，每次取可以取得范围内的最小值就好了
         * 嘿嘿，超出超出时间了。。。。
         * @param num
         * @param k
         * @return
         */
        public String removeKdigits(String num, int k) {

            if (num.length() == k) {
                return "0";
            }

            StringBuilder ret = new StringBuilder();

            int size = num.length();

            int i = 0;
            int begin = 0;
            int end = k;
            while (i < size - k) {
                begin = this.getNum(num, begin, end);
                if (ret.length() == 0 && num.charAt(begin) == '0') {

                } else {
                    ret.append(num.charAt(begin));
                }

                begin++;
                end++;
                i++;
            }

            return "".equals(ret.toString()) ? "0" : ret.toString();

        }

        /**
         * 用来获取该位的最小值
         *
         * @param num
         * @param begin
         * @param end
         * @return
         */
        public int getNum(String num, int begin, int end) {
            if (begin > end) {
                return -1;
            }
            int min = 10;
            int index = -1;
            for (int i = begin; i <= end; i++) {
                if (num.charAt(i) == '0') {
                    return i;
                }
                int temp = Character.getNumericValue(num.charAt(i));
                if (temp < min) {
                    index = i;
                    min = temp;
                }
            }
            return index;
        }


        /**
         * 方法二：
         * 贪心 + 单调栈
         * @param num
         * @param k
         * @return
         */
        public String removeKdigits01(String num, int k) {
            Deque<Character> deque = new LinkedList<Character>();
            int length = num.length();
            for (int i = 0; i < length; ++i) {
                char digit = num.charAt(i);
                while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
                    deque.pollLast();
                    k--;
                }
                deque.offerLast(digit);
            }

            for (int i = 0; i < k; ++i) {
                deque.pollLast();
            }

            StringBuilder ret = new StringBuilder();
            boolean leadingZero = true;
            while (!deque.isEmpty()) {
                char digit = deque.pollFirst();
                if (leadingZero && digit == '0') {
                    continue;
                }
                leadingZero = false;
                ret.append(digit);
            }
            return ret.length() == 0 ? "0" : ret.toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
